package 简单.动态规划;

/**
 * 给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形
 * 成的字符串是 sequence 的一个子字符串，那么单词 word 的 重
 * 复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 
 * 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
 * 给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-repeating-substring
 */
public class 最大重复子字符串_1668 {

    public static void main(String[] args) {

    }

    /**
     * 暴力模拟
     *
     * @param sequence
     * @param word
     * @return
     */
    public int maxRepeating(String sequence, String word) {
        int count = 0;
        StringBuilder repeatStr = new StringBuilder();
        repeatStr.append(word);

        while (repeatStr.length() <= sequence.length()) {

            if (!sequence.contains(repeatStr.toString())) {
                return count;
            }

            count++;
            repeatStr.append(word);
        }

        return count;
    }

    /**
     * 动态规划
     * 子问题：
     * 在 sequence 中以索引 i 结尾的最大重复值是多少
     * 转移方程：
     * 如果以索引 i 往前 word.length() 个字符，正好和 word 相等
     * dp[i] = dp[i-word.length()] + 1
     * 否则
     * dp[i] = 0
     */
    public int maxRepeating2(String sequence, String word) {
        int count = 0;
        int[] dp = new int[sequence.length()];
        int wLen = word.length();

        if (sequence.startsWith(word)) {
            count = 1;
            dp[wLen - 1] = 1;
        }

        for (int i = wLen; i < sequence.length(); i++) {
            if (sequence.substring(i - wLen + 1, i + 1).equals(word)) {
                dp[i] = dp[i - wLen] + 1;
                count = Math.max(count, dp[i]);
            }
        }

        return count;
    }

}
